package day_2022_4_to_7.day48;

import java.util.*;

/**
 * @author haomin
 * @date 2022/07/07 11:54
 **/
public class Day46_1_FindHalfNumber {
    // 方法一
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        return array[array.length/2];
    }


    // 方法二 利用map 键值对
    public int MoreThanHalfNum_Solution2(int [] array) {
        if(array.length == 0 || array ==null){
            return 0;
        }
        int half = array.length >> 1;

        Map<Integer,Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < array.length; i++) {
            if(map.containsKey(array[i])){
                // map中存在当前key 时，value + 1
                map.replace(array[i],map.get(array[i])+1);
            }else {
                // map中不存在当前key 时，存入key,并将value 置为1
                map.put(array[i],1);
            }

            if(map.get(array[i]) > half){
                // 当前key的value值大于数组元素一半时，key就是所求值
                return array[i];
            }
        }
        return 0;
    }

    // 方法三 查询的本质是排除
    public int MoreThanHalfNum_Solution3(int [] array) {
        if(array.length == 0 || array == null){
            return 0;
        }
        int half = array.length >> 1;

        int target = array[0];
        int times = 1;
        for (int i = 1; i < array.length; i++) {
            if(times == 0){
                // 当times == 0时，将当前元素赋值给 target
                target = array[i];
                times = 1;
            }else if(target == array[i]){
                // 当后一个元素与target 相同时，times++
                times++;
            }else {
                // 当后一个元素与target 不相同时，times--
                times--;
            }
        }

        times = 0;
        for (int i = 0; i < array.length; i++) {
            if(target == array[i]){
                times ++;
            }
        }
        return times > half ? target : 0;
    }
}